-module(quardtree2).

-compile(export_all).

-include("map.hrl").

-include_lib("eunit/include/eunit.hrl").

-type vnode() :: {string(), node()}.

-type quardtree_node() :: {_,_,_,_}.
-type node_type() :: quardtree_node() | vnode().

-type quardtree() :: node_type().


-spec new() -> quardtree().
new() ->
    {nil, nil, nil, nil}.

new(VNode) ->
    {VNode, VNode, VNode, VNode}.

new(V0, V1, V2, V3) ->
    {V0, V1, V2, V3}.

-spec add(CellId :: cell_id(), VNode :: vnode(), QuardTree :: quardtree()) -> quardtree().
add([$0], VNode, {_V0,V1,V2,V3} = _QuardTree) ->
    {VNode, V1, V2, V3};
add([$1], VNode, {V0,_V1,V2,V3} = _QuardTree) ->
    {V0, VNode, V2, V3};
add([$2], VNode, {V0,V1,_V2,V3} = _QuardTree) ->
    {V0, V1, VNode, V3};
add([$3], VNode, {V0,V1,V2,_V3} = _QuardTree) ->
    {V0, V1, V2, VNode};
add([$0|Tail], VNode, {Q0,Q1,Q2,Q3} = _QuardTree) ->
    {add(Tail, VNode, Q0), Q1, Q2, Q3};
add([$1|Tail], VNode, {Q0,Q1,Q2,Q3} = _QuardTree) ->
    {Q0, add(Tail, VNode, Q1), Q2, Q3};
add([$2|Tail], VNode, {Q0,Q1,Q2,Q3} = _QuardTree) ->
    {Q0, Q1, add(Tail, VNode, Q2), Q3};
add([$3|Tail], VNode, {Q0,Q1,Q2,Q3} = _QuardTree) ->
    {Q0, Q1, Q2, add(Tail, VNode, Q3)}.

-spec insert(NewVnode::vnode(), Vnode::vnode(), _::quardtree_node()) -> quardtree_node().
%%
%% when using insert(), quardtree MUST have the Vnode
%%
%% +-------+     +---+---+
%% |   V   |     | N | V |
%% |-------|     |-------+
%% |       | to  |       |
%% +-------+     +-------+
insert(NewVnode, Vnode, {Vnode,Vnode,V2,V3}) ->
    {NewVnode, Vnode, V2, V3};
%%
%% +-------+     +-------+
%% |       |     |       |
%% |-------|     |---+---+
%% |   V   | to  | N | V |
%% +-------+     +---+---+
insert(NewVnode, Vnode, {V0,V1,Vnode,Vnode}) ->
    {V0, V1, NewVnode, Vnode};
%%
%% +---+---+     +---+---+
%% |   |   |     | V |   |
%% | V |   |     +---+   |
%% |   |   | to  | N |   |
%% +---+---+     +---+---+
insert(NewVnode, Vnode, {Vnode,V1,Vnode,V3}) ->
    {Vnode, V1, NewVnode, V3};
%%
%% +---+---+     +---+---+
%% |   |   |     |   | V |
%% |   | V |     |   +---+
%% |   |   | to  |   | N |
%% +---+---+     +---+---+
insert(NewVnode, Vnode, {V0,Vnode,V2,Vnode}) ->
    {V0, Vnode, V2, NewVnode};
%%
%%               +---+ +---+
%% +---+---+     | 0 | | 1 |
%% | 0 | 1 |     +---+ +---+
%% |---+---|     +---+ +---+
%% | 2 | 3 | to  | 2 | | 3 |
%% +---+---+     +---+ +---+
insert(NewVnode, Vnode, {V0, V1, V2, V3}) ->
    {insert(NewVnode, Vnode, V0),
        insert(NewVnode, Vnode, V1),
        insert(NewVnode, Vnode, V2),
        insert(NewVnode, Vnode, V3)};
insert(_NewVnode, _Vnode, V) ->
    V.

-spec insert_vertical(NewVnode::vnode(), Vnode::vnode(), _::quardtree_node()) -> quardtree_node().
%%
%% +-------+      +---+---+
%% |       |      |   |   |
%% |   V   |      | N | V |
%% |       |  to  |   |   |
%% +-------+      +---+---+
insert_vertical(NewVnode, Vnode, {Vnode, V1, V2, V3}) ->
    {{NewVnode, Vnode, NewVnode, Vnode}, V1, V2, V3};
insert_vertical(NewVnode, Vnode, {V0, Vnode, V2, V3}) ->
    {V0, {NewVnode, Vnode, NewVnode, Vnode}, V2, V3};
insert_vertical(NewVnode, Vnode, {V0, V1, Vnode, V3}) ->
    {V0, V1, {NewVnode, Vnode, NewVnode, Vnode}, V3};
insert_vertical(NewVnode, Vnode, {V0, V1, V2, Vnode}) ->
    {V0, V1, V2, {NewVnode, Vnode, NewVnode, Vnode}};
insert_vertical(NewVnode, Vnode, {V0, V1, V2, V3}) ->
    {insert_vertical(NewVnode, Vnode, V0),
        insert_vertical(NewVnode, Vnode, V1),
        insert_vertical(NewVnode, Vnode, V2),
        insert_vertical(NewVnode, Vnode, V3)};
insert_vertical(_NewVnode, _Vnode, V) ->
    V.

-spec insert_horizonal(NewVnode::vnode(), Vnode::vnode(), _::quardtree_node()) -> quardtree_node().
%%
%% +-------+      +-------+
%% |       |      |   V   |
%% |   V   |      +-------+
%% |       |  to  |   N   |
%% +-------+      +-------+
insert_horizonal(NewVnode, Vnode, {Vnode, V1, V2, V3}) ->
    {{Vnode, Vnode, NewVnode, NewVnode}, V1, V2, V3};
insert_horizonal(NewVnode, Vnode, {V0, Vnode, V2, V3}) ->
    {V0, {Vnode, Vnode, NewVnode, NewVnode}, V2, V3};
insert_horizonal(NewVnode, Vnode, {V0, V1, Vnode, V3}) ->
    {V0, V1, {Vnode, Vnode, NewVnode, NewVnode}, V3};
insert_horizonal(NewVnode, Vnode, {V0, V1, V2, Vnode}) ->
    {V0, V1, V2, {Vnode, Vnode, NewVnode, NewVnode}};
insert_horizonal(NewVnode, Vnode, {V0, V1, V2, V3}) ->
    {insert_horizonal(NewVnode, Vnode, V0),
        insert_horizonal(NewVnode, Vnode, V1),
        insert_horizonal(NewVnode, Vnode, V2),
        insert_horizonal(NewVnode, Vnode, V3)};
insert_horizonal(_NewVnode, _Vnode, V) ->
    V.

-spec lookup(CellId :: cell_id(), _QuardTree :: quardtree()) -> vnode().
lookup([], _QuardTree) ->
    none;
lookup([$0|Tail], {Node, _, _, _} = _QuardTree) ->
    extract_node(Tail, Node);
lookup([$1|Tail], {_, Node, _, _} = _QuardTree) ->
    extract_node(Tail, Node);
lookup([$2|Tail], {_, _, Node, _} = _QuardTree) ->
    extract_node(Tail, Node);
lookup([$3|Tail], {_, _, _, Node} = _QuardTree) ->
    extract_node(Tail, Node).

-spec extract_node(_::cell_id_scope(), _::node_type()) -> vnode(). 
extract_node(_CellId, {_Str, _Node} = VNode) ->
    VNode;
extract_node(CellId, {_, _, _, _} = QuardNode) ->
    lookup(CellId, QuardNode).

insert_test() ->
    A = {"A", 'a@10.0.0.47'},
    B = {"B", 'b@10.0.0.47'},
    C = {"C", 'c@10.0.0.47'},
    D = {"D", 'd@10.0.0.47'},
    E = {"E", 'e@10.0.0.47'},
    F = {"F", 'f@10.0.0.47'},
    G = {"G", 'g@10.0.0.47'},
    H = {"H", 'h@10.0.0.47'},
    I = {"I", 'i@10.0.0.47'},
    A2 = {"A2", 'a2@10.0.0.47'},
    N1 = {G,H,F,I},
    N2 = {E,D,E,D},
    N3 = {C,B,C,B},
    QuardTree = {N1,A, N2, N3},
    ?assertEqual({N1, {A2,A,A2,A}, N2, N3}, insert_vertical(A2, A, QuardTree)),
    ?assertEqual({N1, {A,A,A2,A2}, N2, N3}, insert_horizonal(A2, A, QuardTree)),
    
    ?assertEqual({{{G,G,A2,A2}, H, F, I}, A, N2, N3}, insert_horizonal(A2,G, QuardTree)),
    ?assertEqual({{{A2,G,A2,G}, H, F, I}, A, N2, N3}, insert_vertical(A2,G, QuardTree)),

    ?assertEqual({{G,{H,H,A2,A2}, F, I}, A, N2, N3}, insert_horizonal(A2,H, QuardTree)),
    ?assertEqual({{G,{A2,H,A2,H}, F, I}, A, N2, N3}, insert_vertical(A2,H, QuardTree)),

    B2 = {"B2", 'b2@10.0.0.47'},
    ?assertEqual({N1, A, N2, {C,B,C,B2}}, insert(B2,B, QuardTree)),
    C2 = {"C2", 'c2@10.0.0.47'},
    ?assertEqual({N1, A, N2, {C,B,C2,B}}, insert(C2,C, QuardTree)),

    N_2 = {E,E,D,D},
    QuardTree2 = {N1, A, N_2, N3},
    E2 = {"E2", 'e2@10.0.0.47'},
    ?assertEqual({N1, A, {E2,E,D,D}, N3}, insert(E2, E, QuardTree2)),
    D2 = {"D2", 'd2@10.0.0.47'},
    ?assertEqual({N1, A, {E,E,D2,D}, N3}, insert(D2, D, QuardTree2)).

add_test() ->
    A = {"A", 'a@10.0.0.47'},
    B = {"B", 'b@10.0.0.47'},
    C = {"C", 'c@10.0.0.47'},
    D = {"D", 'd@10.0.0.47'},
    E = {"E", 'e@10.0.0.47'},
    F = {"F", 'f@10.0.0.47'},
    G = {"G", 'g@10.0.0.47'},
    H = {"H", 'h@10.0.0.47'},
    I = {"I", 'i@10.0.0.47'},
    B2 = {"B2", 'b2@10.0.0.47'},
    N1 = {G,H,F,I},
    N2 = {E,D,E,D},
    N3 = {C,B,C,B},
    QuardTree = {N1,A,N2,N3},
    NewQT = add("31", B2, QuardTree),
    ?assertEqual(B2, lookup("31", NewQT)).

lookup_test_() ->
    A = {"A", 'a@10.0.0.47'},
    B = {"B", 'b@10.0.0.47'},
    C = {"C", 'c@10.0.0.47'},
    D = {"D", 'd@10.0.0.47'},
    E = {"E", 'e@10.0.0.47'},
    F = {"F", 'f@10.0.0.47'},
    G = {"G", 'g@10.0.0.47'},
    H = {"H", 'h@10.0.0.47'},
    N1 = {A,A,H,G},
    N2 = {F,F,E,E},
    N3 = {C,C,D,D},
    QuardTree = {N1, B, N2, N3},

    VNa = lookup("00", QuardTree),
    [
        ?_assertEqual(A, VNa),
        ?_assertEqual(A, lookup("01", QuardTree)),
        ?_assertEqual(B, lookup("1", QuardTree)),
        ?_assertEqual(H, lookup("02", QuardTree)),
        ?_assertEqual(G, lookup("03", QuardTree)),
        ?_assertEqual(F, lookup("20", QuardTree)),
        ?_assertEqual(F, lookup("21", QuardTree)),
        ?_assertEqual(E, lookup("22", QuardTree)),
        ?_assertEqual(C, lookup("30", QuardTree)),
        ?_assertEqual(C, lookup("31", QuardTree)),
        ?_assertEqual(D, lookup("32", QuardTree)),
        ?_assertEqual(D, lookup("33", QuardTree))
    ].
